package 滑动窗口.无重复最长子串;

import java.util.HashSet;
import java.util.Set;

/**
 * 核心思路
 * 我们能不能用两个指针维护一个[当前不重复的子串]
 * 然后一边往右扫，一边更新最常长度
 * 这个就加滑动窗口
 * */
/**
 * 题目思路
 * 定义两个指针：
 * left：窗口的左边界(子串的起点)
 * right 窗口的右边界(子串的终点)
 * 当前窗口：[left,right]始终保持：里面没有重复的字符
 * 然后：
 * right一直往右移动，一个字符一个字符的读
 * 每来一个新字符
 * 如果不重复，就把它加入窗口，更新最大长度
 * 如果重复，就把left往右挪，缩小窗口，直到把重复的字符移除
 * */

class Solution1 {
    public int lengthOfLongestSubstring(String s) {
        // 用一个集合来记录当前窗口里有哪些字符
        Set<Character> window = new HashSet<>();
        int left = 0; // 窗口左边界
        int res = 0; // 最长不重复子串的长度

        // right是窗口右边界，遍历整个字符串
        for(int right = 0;right < s.length();right++){
            char c = s.charAt(right);
            
            // 如果当前字符在窗口里已经出现过，就不断移动left
            // 把左边字符从集合里移除，直到把这个重复的字符串移除窗口
            while(window.contains(c)){
                window.remove(s.charAt(left));
                left++;
            }

            // 此时c不在窗口里，可以安全加入
            window.add(c);

            // 更新答案；当前窗口长度是right - left + 1
            res = Math.max(res,right - left + 1);
        }
        return res;
    }
}